
public class LeetCode76 {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        int required = 0;
        for (char c : t.toCharArray()) {
            if (need[c] == 0) {
                required++;
            }
            need[c]++;
        }
        //滑动窗口
        int[] window = new int[128];
        int left = 0, valid = 0;
        int maxLen = Integer.MAX_VALUE;
        String res = "";
        for (int right = 0; right < s.length(); right++) {
            char rc = s.charAt(right);
            // 如果当前字符是t中的字符，则更新窗口计数
            if (need[rc] > 0) {
                window[rc]++;
                // 当窗口内该字符数量达到需求时，valid+1
                if (window[rc] == need[rc]) {
                    valid++;
                }
            }
            //收缩逻辑
            while (valid == required) {
                // 更新最小窗口结果
                int cur = right - left + 1;
                if (cur < maxLen) {
                    maxLen = cur;
                    res = s.substring(left, right + 1);
                }

                //移动左指针
                char lc = s.charAt(left);
                if (need[lc] > 0) {
                    // 如果移除的是关键字符，valid-1
                    if (window[lc] == need[lc]) {
                        valid--;
                    }
                    window[lc]--;
                }
                left++;
            }
        }

        return res;
    }
}
